Loading…

Nombres de Catalan :

Yvik Swan

Updated April 20, 2016

Transcript

Les tâches du mathématicien sont multiples :

Prouver ...

Pensez à un nombre à deux chiffres.

Exemple : 21

Sommez les chiffres de ce nombre.

Trouvez votre nombre dans le tableau ci-dessous et fixez le symbole correspondant pendant 10 secondes.

Exemple : 2+1 = 3

Soustrayez le résultat obtenu du nombre dont

vous êtes partis.

Exemple : 21-3

Théorème :

La différence entre un entier à deux chiffres et la somme de ses chiffres est toujours un multiple de 9.

Tous les sont associés à des multiples de 9!

Démonstration :

Tout nombre a deux chiffres s'écrit

a*10 + b

Je savais donc, en vous faisant faire ce calcul, que vous alliez nécessairement tomber sur un multiple de 9!

Donc

(a*10+b) - (a+b)

= a*10 + b - a - b

= a*(10-1)

= a*9

Est-ce de la magie?

Non!

qui est bien un multiple de 9!

Qu'est-ce qui explique ce qui vient de se passer?

Je savais quel nombre vous alliez choisir?

Non!

Je savais sur quel nombre vous alliez tomber?

Non!

Je savais sur quel symbole vous alliez tomber?

Ben oui!

Compter ...

Résoudre ...

Combien y a-t-il de résultats (Pile, Face) possibles

quand on lance une pièce de monnaie?

On lance 1 fois :

2 résultats (P ou F)

On lance 2 fois :

Que fait un mathématicien

Ce qui mène à la suite de nombres :

2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, ...

4 résultats

(P, P) ou (P, F) ou (F, P) ou (F, F)

On lance 3 fois :

8 résultats

(P, P, P) ou (P, P, F) ou (P, F, P) ou (F, P, P) ou (P, F, F) ou (F, P, F) ou (F, F, P) ou (F, F, F)

Plus généralement on introduit les nombres :

On lance k fois :

qui répondent à la question "Combien y a-t-il de façons de placer n objets sur k positions?"

Pour des questions plus compliquées, il faut réfléchir un peu plus et faire appel à des constructions de plus en plus sophistiquées :

Congruences

Schensted

Groupes de permutations

Ce qui mène à la suite de nombres :

1, 2, 6, 24, 120, 720, 5040, 40320, 362880...

Déterminant de Toeplitz

Combien y a-t-il de façons de ranger k objets?

Arrangements

1 objet :

Combinaisons

Plus généralement on introduit les nombres :

1 seule façon

Nombres de Stirling

2 objets :

Diagrammes de Young

2 façons : AB ou BA

3 objets :

Partitions

6 façons :

Les mathématiques Grecques

620 BC - 500 AD

Mésopotamie, Irak-Syrie

Civilisation Sumérienne,

±4 000 BC

Egypte

±3 000 BC

Les mathématiques Indiennes

400 AD - 1600 AD

Ishango, Nord Kivu, Congo

±20 000 ans?

Aujourd'hui, la race humaine a vaincu et maîtrise la planète : les eaux, les forêts, le ciel, ... rien ne lui a résisté.

Comment cela est-il arrivé?

L'homme est malin...

Les nombres de Catalan

Yvik Swan, ULg

If people don’t believe that mathematics is simple, it’s only because they don’t realize how complicated life is.

John von Neumann (1903 - 1957)

qui répondent à la question "Combien y a-t-il de façons de placer k objets en ligne?"

0 1 2 3 4 5 6 7 8 9

ABC ou ACB ou BCA ou BAC ou CAB ou CBA

10 11 12 13 14 15 16 17 18 19

Nous sommes intelligents mais, au fond, pas vraiment plus que des chimpanzés!

Le secret de notre succès est surtout notre insatiable curiosité.

20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

Et plus l'homme trouvait de réponses, plus il trouvait de questions...

Une des plus célèbres suites non triviales est donnée par le triangle de Pascal :

Que signifie être divisible?

La soif de réponses a mené au développement de la théorie des nombres, du calcul différentiel, de l'algèbre, de la géométrie, de l'analyse, de la topologie, de la théorie du calcul des probabilités, des statistiques...

Y a-t-il d'autres nombres que les nombres pour compter?

Quels sont tous les nombres qui n'ont "pas" de diviseurs?

40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

et, chemin faisant, à la révolution industrielle et l'avènement de l'ère technologique à travers la création des ordinateurs, de l'internet, le développement de la robotique et l'explosion de la puissance de l'intelligence artificielle...

Y a-t-il plus de fractions que de nombres entiers?

Qu'est-ce que l'infini?

0 1 2 3 4 5 6 7 8 9

Quels sont tous les nombres "divisibles" par 3?

10 11 12 13 14 15 16 17 18 19

20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

... et à l'iphone 6.

80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120

121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 191 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 281 283 284 285 286

0 1 2 3 4 5 6 7 8 9

...........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

10 11 12 13 14 15 16 17 18 19

Quels sont tous les nombres "divisibles" par 2?

20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120

0 1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19

Où va nous mener la révolution scientifique

actuelle?

20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120

A terme, les experts prédisent une explosion d'intelligence qui rendra les machines plus intelligentes que nous.

I visualize a time when we will be to robots what dogs are to humans.

Claude E. Shannon

Ils arrivent ...

Aidez-nous à sauver l'humanité : devenez mathématicien!!

dont les entrées sont les nombres

1 1

etc.

Les nombres de Catalan sont donnés par la formule

Et, en poursuivant ainsi le long de notre curiosité, chaque problème de dénombrement va donner naissance à une suite de nombres dont chaque entrée sera la réponse à une question particulière...

qui répondent aux questions "de combien de façons peut-on mélanger a objets d'un certain type avec b objets d'un autre type?"

Généraliser ...

et on calcule

Inventer ...

Et maintenant, une petite pause.

Et au moins 203 autres problèmes de dénombrement!

"De combien de façons n personnes assises autour d'une table circulaire peuvent-elles se serrer la main simultanément sans que des bras ne se croisent?"

"De combien de façons peut-on trianguler un polygone?"

Source : http://www-math.mit.edu/~rstan/ec/

"Dans une grille de n×n carrés, combien y a-t-il de chemins de longueur 2n qui mènent du coin supérieur gauche au coin inférieur droit sans passer sous la diagonale ?"

"Combien y a-t-il de façons d’agencer n paires de parenthèses de façon à ce que chaque parenthèse ouverte ait, à sa droite, la parenthèse fermée correspondante ?"

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

Ces nombres sont également solution d'autres problèmes du même type!

On calcule les formules équivalentes

On a fini!!

"Combien y a-t-il de chemins de (0, 0) à (2n-1, -3)?"

Le nème Nombre de Catalan est la réponse à la question :

"combien y a-t-il de chemins qui mènent de (0, 0) à (2n, 0) sans passer en dessous de l'axe 0?"

Distance à l'origine

et donc

Question : combien y a-t-il de trajectoires qui mènent notre ami à son point de départ

sans passer à travers le mur?

Nombre de pas

"Combien y a-t-il de chemins de

(0, 0) à (2n-1, -3)?"

Pour aller de (0, 0) à (2n-1, -3)

Un chemin est une succession de pas vers le Haut et de pas vers le Bas.

il faut 2n-1 pas au total

"Combien y a-t-il de façons de mélanger

n-2 "H" et n+1 "B" ?"

il faut 3 "B" de plus que de "H"

il faut n-2 "H" et n+1 "B"

Exemple : Le chemin

H, H, B, B, B, B, B mène de (0, 0) à (7, -3)

n=4

1 seule façon

En 2 pas :

n=1

n=5

En 4 pas :

n=2

2 façons

Contrainte #1 : le premier pas doit s'effectuer vers le haut

n=3

n=6

132

5 façons

En 6 pas :

Il y a autant de trajectoires de (0,0) à (2n, 0) qui commencent par un pas vers le haut

"Combien y a-t-il de chemins de (0, 0) à (2n-1, -1)?"

Peut-on les calculer???

Considérons d'abord les deux contraintes :

Quels sont ces nombres?

En reprenant la Contrainte #1 on cherche le nombre de trajectoires de (0, 0) à (2n-1, -1) qui ne franchissent pas l'axe y=-1

On les appelle Nombres de Catalan

Bien sûr!!

Visualisons un chemin comme une succession de pas vers le Haut et de pas vers le Bas.

Le nombre de trajectoires au total

Pour aller de (0, 0) à (2n-1, -1)

Le nombre de trajectoires qui ne touchent pas l'axe

le nombre de trajectoires qui touchent l'axe.

Contrainte #2 : interdit de passer sous l'axe y=0.

Les chemins

"Combien y a-t-il de chemins de (0, 0) à (2n-1, -1)?"

H H H B B B B

mènent de (0, 0) à (7, -1)

H B H B H B B

Exemple : Le chemin

H, H, H, B, B, B, B mène de (0, 0) à (7, -1)

il faut 2n-1 pas au total

B B B B H H H

En général:

B B B H B H H

il faut 1 "B" de plus que de "H"

....

"Combien y a-t-il de façons de mélanger

n-1 "H" et n "B" ?"

Combien y a-t-il de tels chemins?

il faut n-1 "H" et n "B"

Toute succession de n-1 "H" et n "B"

(peu importe l'ordre!)

mènera de (0, 0) à (2n-1, -1).

Autant qu'il y a de façons de mélanger 3 "H" et 4 "B" :

Distance à l'origine

Il y a donc autant de chemins de (0,0) à (2n-1, -1)

qu'il y a de suites de n-1 "H" et n "B"

le nème nombre de Catalan est :

(i) les trajectoires de (0,0) à (2n-1, -1)

(ii) les trajectoires de (0, 0) à (2n-1, -3)

Pour calculer les Nombres de Catalan il suffit donc de compter

Le principe de réflexion

(i) - (ii)

Il y a autant de trajectoires

de (0, 0) à (2n-1, -1)

qui touchent l'axe bleu

Le nème nombre de Catalan répond à la question :

"Combien y a-t-il de chemins qui mènent

de (0,0) à (2n, 0)

sans passer en dessous de 0?"

Nombre de pas

résultats

Pythagore (±500 BC)

Archimède (± 250 BC)

objets :

que de trajectoires de (1, 1) à (2n, 0) ....

Le nème Nombre de Catalan est

"combien y a-t-il de chemins qui mènent de (0, 0) à (2n, 0) sans passer en dessous de l'axe 0?"

Cette question est équivalente à :

"combien y a -t-il de chemins qui mènent de (0, 0) à (2n-1, -1) sans toucher l'axe -2?"

mur

Aryabhata (±500 AD)

Brahmagupta (±650 AD)

"combien y a -t-il de chemins qui mènent de (0, 0) à (2n-1, -1) sans toucher l'axe -2?"

Réponse : autant qu'il y a de chemins de (0, 0) à (2n-1, -1) dont on soustrait le nombre de chemins de (0, 0) à (2n-1, -3)

donc le nombre de trajectoires de (0, 0) à (2n-1, -1) qui ne touchent pas l'axe y=-2?

trajectoires de (0, 0) à (2n-1, -1) qui ne franchissent pas l'axe y=-1

le nombre de

façons

que de trajectoires

de (0, 0) à (2n-1, -3)

que de trajectoires de (1, 1) à (2n, 0) ....

ou même de trajectoires de (0, 0) à (2n-1, -1)

Qu'y a-t-il de spécial concernant le symbole dans le tableau?